package 力扣.二分;

import java.awt.peer.CanvasPeer;
import java.math.BigInteger;
import java.util.Arrays;

public class 子数组的最大平均值II_LintCode617 {
    public double maxAverage(int[] nums, int k) {
        if (nums == null || nums.length == 0){
            return  -1;
        }
        //寻找数组中的最大值、最小值
        double small = Double.MAX_VALUE;
        double large = Double.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int te = nums[i];
            small = Math.min(small, te);
            large = Math.max(large, te);
        }
        double l = small,r = large + 1;
        while (r - l > 1e-6){
            double m = l + ((r - l) / 2.0);
            int pos = getC1(nums,m,k);
            if (pos < 0){
                l = m;
            }else {
                r = m;
            }
        }
        return l ;
    }

    /**
     * 寻找平均值为m,且长度大于等于K的子数组
     * 1.建立一个新数组，新数组的值都为nums中的元素减去平均值m
     * 2、求新数组中的最大子序和是否大于零？
     *    使用落差法+前缀和
     *    还要保证子数组长度大于k——》使用滑动窗口k.保证最小落差在窗口之外
     *
     * @param nums
     * @param m
     * @return
     */
    private int getC1(int[] nums, double m,int k) {
        int N = nums.length;
        double[] B = new double[N];
        for (int i = 0; i < N; i++) {
            B[i] = (double) nums[i] - m;//全部减去平均值
        }
        //求B数组的最大子序和
//        int pre = 0;
//        int[] C = new int[N];
        double pre_MIN = 0.0;
//        double ans = Double.MIN_VALUE;

        for (int i = 1; i < N; i++) {//自己变成自身的前缀和
            B[i] += B[i-1];
        }
        for (int i = k - 1; i < N; i++) {

            if (B[i] >= pre_MIN){
                return 0;
            }
            pre_MIN = Math.min(pre_MIN, B[i - k + 1]);
        }
        return -1;
    }
}
